/**
 * A feladat a bemenő gráfban megtalálni a leghosszabb utat.
 * 
 * Az ütemterveket megvalósító osztály. Három algoritmust tartalmaz. Az első
 * mindig a legtovább tartó feladatot választja. A második mindig a legrövidebb
 * ideig tartó feladatot választja. A harmadik egy optimálisabb megoldást
 * választ, minden forrásból felépít egy mélységi feszítőfát és ezek közül
 * választja ki a leghosszabb utat.
 * 
 * @author Gasztány Richárd
 * 
 */
public class Utermterv {

	private static int[] tavolsag;
	private static int[] apa;
	private static int maxtav;
	private static String maxut;
	private static Graf graf;
	private static long runningTime1;
	private static long runningTime2;

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		graf = new Graf();

		// graf.kiIr();

		runningTime1 = System.currentTimeMillis();
		algoritmus1();
		runningTime2 = System.currentTimeMillis();
		System.out.println("Futási idő algoritmus1: " + (runningTime2 - runningTime1));

		runningTime1 = System.currentTimeMillis();
		algoritmus2();
		runningTime2 = System.currentTimeMillis();
		System.out.println("Futási idő algoritmus2: " + (runningTime2 - runningTime1));

		runningTime1 = System.currentTimeMillis();
		algoritmus3();
		runningTime2 = System.currentTimeMillis();
		System.out.println("Futási idő algoritmus3: " + (runningTime2 - runningTime1));

	}

	/**
	 * mindig a legtovább tartó feladatot választja
	 */
	private static void algoritmus1() {
		int max = 0;
		int maxIndex = -1;
		for (int i = 0; i < graf.getCsucsokSzama(); i++) {

			if (graf.getCsucsok()[i].getBeEl().isEmpty()) {
				if (max < graf.getCsucsok()[i].getIdotartam()) {
					max = graf.getCsucsok()[i].getIdotartam();
					maxIndex = i;
				}
			}
		}
		if (maxIndex == -1) {
			System.out.println("Hiba");
		} else {
			int maxut = graf.getCsucsok()[maxIndex].getIdotartam();
			while (!graf.getCsucsok()[maxIndex].getKiEl().isEmpty()) {
				System.out.print((char) (maxIndex + 'A') + " -> ");
				java.util.Iterator<Integer> it = graf.getCsucsok()[maxIndex].getKiEl().iterator();
				max = 0;
				while (it.hasNext()) {
					int index = it.next();
					if (max < graf.getCsucsok()[index].getIdotartam()) {
						max = graf.getCsucsok()[index].getIdotartam();
						maxIndex = index;
					}
				}
				maxut += max;
			}
			System.out.print((char) (maxIndex + 'A') + " -> ");
			System.out.println(maxut);
		}
	}

	/**
	 * legrövidebbet először
	 */
	private static void algoritmus2() {
		int min = Integer.MAX_VALUE;
		int minIndex = -1;
		for (int i = 0; i < graf.getCsucsokSzama(); i++) {

			if (graf.getCsucsok()[i].getBeEl().isEmpty()) {
				if (min > graf.getCsucsok()[i].getIdotartam()) {
					min = graf.getCsucsok()[i].getIdotartam();
					minIndex = i;
				}
			}
		}
		// System.out.println("maxindex:" + (char) ('A' + maxIndex));
		// System.out.println("maxindex:" + maxIndex);
		// System.out.println(graf.getCsucsok()[maxIndex].getIdotartam());
		if (minIndex == -1) {
			System.out.println("Hiba");
		} else {
			int maxut = graf.getCsucsok()[minIndex].getIdotartam();
			while (!graf.getCsucsok()[minIndex].getKiEl().isEmpty()) {
				System.out.print((char) (minIndex + 'A') + " -> ");
				java.util.Iterator<Integer> it = graf.getCsucsok()[minIndex].getKiEl().iterator();
				min = Integer.MAX_VALUE;
				while (it.hasNext()) {
					int index = it.next();
					if (min > graf.getCsucsok()[index].getIdotartam()) {
						min = graf.getCsucsok()[index].getIdotartam();
						minIndex = index;
					}
				}
				maxut += min;
			}
			System.out.print((char) (minIndex + 'A') + " -> ");
			System.out.println(maxut);
		}
	}

	/**
	 * mélységi keresés alapján választja a leghosszabb utat
	 */
	private static void algoritmus3() {
		maxtav = 0;
		maxut = "";
		for (int i = 0; i < graf.getCsucsokSzama(); i++) {
			if (graf.getCsucsok()[i].getBeEl().isEmpty()) {
				tavolsag = new int[graf.getCsucsokSzama()];
				apa = new int[graf.getCsucsokSzama()];
				for (int j = 0; j < graf.getCsucsokSzama(); j++) {
					apa[j] = -1;
				}
				tavolsag[i] = graf.getCsucsok()[i].getIdotartam();
				melysegi(i);
				int maxend = -1;
				for (int j = 0; j < graf.getCsucsokSzama(); j++) {
					if (maxtav < tavolsag[j]) {
						maxtav = tavolsag[j];
						maxend = j;
						maxut = "";
					}
				}
				if (maxend != -1) {
					int index = maxend;
					maxut += (char) (index + 'A');
					index = apa[index];
					while (index != -1) {
						maxut += (char) (index + 'A');
						index = apa[index];
					}
				}

				// for (int j = 0; j < graf.getCsucsokSzama(); j++) {
				// System.out.print("  tav: " + tavolsag[j]);
				// }
				// System.out.println();
				// for (int j = 0; j < graf.getCsucsokSzama(); j++) {
				// System.out.print("  apa: " + apa[j]);
				// }
				// System.out.println();

			}
		}

		for (int i = maxut.length() - 1; i >= 0; i--) {
			System.out.print(maxut.charAt(i) + " -> ");
		}
		System.out.println(maxtav);
	}

	private static void melysegi(int index) {
		java.util.Iterator<Integer> it = graf.getCsucsok()[index].getKiEl().iterator();
		while (it.hasNext()) {
			int i = it.next();
			if (tavolsag[i] < tavolsag[index] + graf.getCsucsok()[i].getIdotartam()) {
				tavolsag[i] = tavolsag[index] + graf.getCsucsok()[i].getIdotartam();
				apa[i] = index;
			}
			melysegi(i);
		}
	}
}
